Міністерство освіти та науки України
Національний університет «Львівська політехніка»
Кафедра автоматизованих систем управління
Лабораторна робота №5
з дисципліни
«Комп’ютерна графіка»
на тему:
“Метод цифрового диференціального аналізатора”
Мета: Освоїти розкладання відрізка в растр методом цифрового диференціального аналізатора.
ТЕОРЕТИЧНІ ОСНОВИ
Один з методів розкладання відрізка в растр полягає в розв’язуванні диференціального рівняння, що описує цей процес. Для прямої лінії маємо
dy/dx=const чи Dy/Dx=(y2-y1)/(x2-x1)
Розв’язок представляється у вигляді
yi+1=yi+Dy
yi+1=yi+Dx(y2-y1)/(x2-x1) [1]
де x1, y1 і x2, y2 - кінці відрізка, що розкладається, і yi - початкове значення для чергового кроку вздовж відрізка. Фактично рівняння [1] являє собою рекурентне співвідношення для послідовних значень y вздовж потрібного відрізка. Цей метод, використовуваний для розкладання в растр відрізків, називається цифровим диференціальним аналізатором (ЦДА). У простому ЦДА або Dx, або Dy (більше із збільшень) вибирається як одиниця растра. Нижче наводиться простий алгоритм, що працює у всіх квадрантах:
Процедура розкладання в растр відрізка по методу цифрового диференціального аналізатора (ЦДА)
передбачається, що кінці відрізка (x1, y1) і (x2, y2) не збігаються
Integer - функція перетворення дійсного числа в ціле.
Sign - функція, що повертає -1, 0, 1 для від’ємного, нульового і додатнього аргументу відповідно
апроксимуємо довжину відрізка
if abs(x2-x1)>=abs(y2-y1) then
Довжина=abs(x2-x1)
else
Довжина=abs(y2-y1)
end if
назначаємо більше із збільшень Dx чи Dy рівним одиниці растра
Dx=(x2-x1)/Довжина
Dy=(y2-y1)/Довжина
округляємо величини, а не відкидаємо дробову частину
використання знакової функції робить алгоритм придатним для всіх квадрантів
x=x1+0.5*Sign(Dx)
y=y1+0.5*Sign(Dy)
початок основного циклу
i=1
while (i<=Довжина)
Plot (Integer(x), Integer(y))
x=x+Dx
y=y+Dy
i=i+1
end while
finish
Наведемо приклад ілюструючий роботу алгоритму:
Приклад 2.1. Простий ЦДА в першому квадранті
Розглянемо відрізок із точки (0,0) у точку (5,5). Використовуємо ЦДА для розкладання цього відрізка в растр. Результати роботи алгоритму такі:
початкові установки
x1=0
y1=0
x2=5
y2=5
Довжина=5
Dx=1
Dy=1
x=0,5
y=0,5
результати роботи покрокового циклу
i
Plot
x
y
0,5
0,5
1
(0,0)
1,5
1,5
2
(1,1)
2,5
2,5
3
(2,2)
3,5
3,5
4
(3,3)
4,5
4,5
5
(4,4)
5,5
5,5
Отримане растрове представлення відрізка зображене на рис.2.1. Зауважимо, що кінцеві точки визначені точно, обрані піксели рівномірно розподілені вздовж відрізка. Однак якщо початковим значенням змінної і взяти нуль замість одиниці, то виявиться активованим піксел з координатами (5,5), що небажано. Якщо адреса піксела задана цілими координатами лівого нижнього кута, то активація цього піксела дасть явно невірну кінцеву точку відрізка (рис.2.1). До того ж при кресленні серії послідовних відрізків піксел (5,5) буде активований двічі: наприкінці даного відрізка і на початку наступного. Такий піксел може виглядати як більш яскравий чи мати інший колір. Наведемо приклад ілюструючий роботу алгоритму в третьому квадранті.
Рис.2.1. Результати роботи простого ЦДА в першому квадранті.
Розглянемо відрізок із точки (0,0) у точку (-8,-4) в третьому квадранті. Використовуємо ЦДА для розкладання цього відрізка в растр. Результати роботи алгоритму такі:
початкові установки
x1=0
y1=0
x2=-8
y2=-4
Довжина=8
Dx=-1
Dy=-0,5
x=-0,5
y=-0,5
результати роботи покрокового циклу
Plot
x
y
-0,5
-0,5
1
(-1,-1)
-1,5
-1,0
2
(-2,-1)
-2,5
-1,5
3
(-3,-2)
-3,5
-2,0
4
(-4,-2)
-4,5
-2,5
5
(-5,-3)
-5,5
-3,0
6
(-6,-3)
-6,5
-3,5
7
(-7,-4)
-7,5
-4,0
8
(-8,-4)
-8,5
-4,5
Незважаючи на те що результати, представлені на рис.2.2, виглядають цілком прийнятними, аналіз відрізків, проведених із точки (0,0) у точку (-8,4) і (8,-4),...